\documentclass[letterpaper, 11 pt, conference]{ieeeconf}  % Comment this line out
                                                          % if you need a4paper
%\documentclass[a4paper, 10pt, conference]{ieeeconf}      % Use this line for a4
                                                          % paper

\IEEEoverridecommandlockouts                              % This command is only
                                                          % needed if you want to
                                                          % use the \thanks command
\overrideIEEEmargins
% See the \addtolength command later in the file to balance the column lengths
% on the last page of the document



% The following packages can be found on http:\\www.ctan.org
\usepackage{graphics} % for pdf, bitmapped graphics files
\usepackage{pdfpages}
%\usepackage{epsfig} % for postscript graphics files
%\usepackage{mathptmx} % assumes new font selection scheme installed
%\usepackage{times} % assumes new font selection scheme installed
%\usepackage{amsmath} % assumes amsmath package installed
%\usepackage{amssymb}  % assumes amsmath package installed
\usepackage{listings}
\lstset{
	basicstyle=\small,
	columns=fullflexible
}

\title{\LARGE \bf
Simulation and Optimization of a Collaborative Multi-Robot Heterogeneous Firefighting System
}

%\author{ \parbox{3 in}{\centering Huibert Kwakernaak*
%         \thanks{*Use the $\backslash$thanks command to put information here}\\
%         Faculty of Electrical Engineering, Mathematics and Computer Science\\
%         University of Twente\\
%         7500 AE Enschede, The Netherlands\\
%         {\tt\small h.kwakernaak@autsubmit.com}}
%         \hspace*{ 0.5 in}
%         \parbox{3 in}{ \centering Pradeep Misra**
%         \thanks{**The footnote marks may be inserted manually}\\
%        Department of Electrical Engineering \\
%         Wright State University\\
%         Dayton, OH 45435, USA\\
%         {\tt\small pmisra@cs.wright.edu}}
%}

\author{Dimitrios Bakllas and Aaron Fineman and Tanay Shah% <-this % stops a space
}


\begin{document}

\maketitle
\thispagestyle{empty}
\pagestyle{empty}


\begin{abstract}

This paper will attempt to create a simulation of a multi-agent autonomous mapping system with the purpose of firefighting. The main focus will be on the scalability of the algorithm and optimization of the system for fast response and optimum use of resources. The system will be a heterogeneous swarm including scouting robots and firefighting robots (which are assumed to be scarce resources.) The metrics of the system will be based on time of completion, effectiveness, and distance traveled. The simulations are geared towards finding an optimum number of robots for a medium sized floor plan (approximately 2000-4000 sq.ft.). Implementation of the simulation will be accomplished using the open source Player-Stage robot simulator.

\end{abstract}

\section{INTRODUCTION}
Multi-robot system (MRS) has been an active area of research for decades. The purpose of using MRS is to simplify a task by assigning the same task to multiple robots which in turn will simplify and shorten the time to completion. Each robot in the system moves through the search space by following the best experience of its own and its colleagues to obtain an optimal solution. To implement MRS in this project there will be a need for mapping the partially known area. Simultaneous Localization and Mapping (SLAM) is a fundamental idea in mobile robotics research. In a SLAM problem a mobile robot explores and senses an unknown region, constructs a map, and localizes itself in the map.

The agents will make use of a distributed control algorithm that receives external commands. The overall goal of the project will be to map a building that is on fire, and then to extinguish the fire. The robots will update the preloaded blueprint of the building with locations of obstructions, local fires, and updated structural information. This multi robot system will be heterogeneous with scouting robots and firefighting robots. The main concern is the scalability of the algorithm across one, several, and many sized systems. For modeling purposes there are going to be several assumptions to constrain the problem space. Main assumptions are that the blueprint of the building is known in advance and that it is fairly up to date. In addition, the robots will have limited communication range to simulated wireless communications in a non-ideal environment. Another constraint added is that the simulation is occurring on a single large floor, rather than worrying about simulating stairs and intra-floor communication. The simulation starts by placing all the robots immediately inside the main door and then activating them.

The initial plan is to create a four dimensional map of obstructions encountered. The axes that are going to be used are X, Y, certainty, and fire. X and Y will be the coordinates that line up with X and Y on the blueprint. Certainty and fire would range from the hex values 00 to FF detailing how certain the agent is of obstructions and how serious the fire is. This allows the agent to integrate other's maps into its own knowledge base with different trust-values, and for its certainty of obstructions to decay over time (it is more likely for collapses to increase over time, not clear out). Fire both allows an agent to mark fire-obstructions and lets it guess how the fire is spreading. This can allow the agent to predict the likely danger of areas and prioritize areas that may become blocked off. This four dimensional map can be easily encoded into a bitmap storing the additional axes in the RGB values. This will allow for the certainty and fire to be easily visualized as shades on a standard bitmap image. The next important part of the simulation is the types of robots and how they will communicate in order to signal firefighting robots to move towards the fire.

The paper is organized as follows. Section II presents the simulation overview. The assumptions of the simulation are described in Section III. Section IV provides the simulation system. Section V discusses about the robots. Section VI summarizes the timeline for the project.  Section VII concludes the paper.


\section{SIMULATION OVERVIEW}
This project will make use of a simulation, due to the dangerous conditions, the cost of creating a staging area, and the availability of robots to form a heterogeneous swarm. The simulation software used is Player-Stage, a popular open-source robot simulator.

Use of a simulation allows for easy changes to the building floor plans, in addition to very quick customizations, which cannot be replicated in the real world. In addition, the environment is fully destructible with no consequences, and can be trivially reverted. However, what should be noted is that the simulations abstract out many important aspects of the real world. In simulations, robots will not take heat or fire damage, their destruction is binary. Battery charge and life can only be estimated. In this simulation, it is assumed to be infinite in this case. The robots are not burdened by their load or terrain. As such, all measurements are perfect, and not reflective of the real world conditions.

\begin{figure}
	\begin{center}
		\leavevmode
		\includegraphics{flow_chart}
	\end{center}
	\caption{A flowchart showing robot progression}
	\label{fig:flowchart}
\end{figure}

\subsection{Group Task}
As shown in Figure \ref{fig:flowchart}, the main structure of the system will initialize at the entrance of the building. From there will be different dispersion techniques that will allow for optimization of the system. The main task for the scouting robots will be to locate fires. At the same time firefighting robots will attempt to position themselves at a convenient location in each room. Once a fire has been located by a scout, the scout will attempt to pass a message to nearby robots that there is a fire and a firefighter is needed. A firefighter will have to prioritize according to the various algorithm being tested and see to which fire it will attend to first. Once the scout receives confirmation from the firefighting robot the scout will return to its original search for more fires. There will need to be an established order for firefighting because firefighters are considered scarce resource.

\subsection{Robot Interactions}
All robot interaction is through a simulated wireless connection. Because infinite range communication is not being used, an abstraction layer must be supplied to handle the range limitations. All communications are assumed to be multicast; all robots in range receive anything sent out. Each time a robot wishes to send a message, a list of all robots within range are compiled, and a message is sent directly to each robot sequentially (simulated multi-cast.)

\subsection{Robot Internal Data}
While there is a lot of data potentially available to the robots, they will be making use of only a limited amount. As stated above, the robots will be working under a bad-case assumption (close to a worst-case assumption.) The robots will have the input of basic mapping sensors available to them, including sonar, IR, and odometry. While Stage makes absolute XY world coordinates available to the robot, these will not be used.


\section{SIMULATION ASSUMPTIONS}

\subsection{Robots}
The heterogeneous swarm of robots will be made up of various amounts of mapping robots (one, a few, several, and many) and a smaller amount of firefighting robots. The firefighting robots will be a limited resource, and their numbers scaled accordingly. All of the robots will be relatively heat resistant, but not impervious to fire and rubble. The robots will be able to move over varied terrain fairly easily, but cannot traverse large piles of rubble. The firefighting robots will be relatively slower than the mapping robots due to their carrying of extinguishing agents. It is assumed in this simulation that the firefighting robots have an infinite supply of extinguishing agent. All robots will be assumed to have an infinite supply of battery.

\subsection{Robot Communication}
The program will attempt to simulate communication in a non-ideal environment. To accomplish this, the robots will have a limited communication range due to the smoky environment (approximately 50 meters at the time of this draft). Firefighter robots have a larger range of communication (roughly double) due to size and more powerful equipment. This might become a miscommunication issue since firefighting robots have the range to pick up surrounding scouts but not necessarily hear their broadcast. The system will not deal with dropped connections, and assume that if a robot is in range, the connection will not be lost except in case of malfunction or destruction.

\subsection{Sensors}
It is assumed that even though the environment is rather smoky, and presents poor or occluded vision, mapping sensors remain fairly accurate, with only their standard variance.

\subsection{Environment}
The environment is largely observable, however, it is non-deterministic. The fire is generated and spreads randomly as a function of time. In addition, debris fall from the ceiling randomly, also as a function of time, and may entrap robots.


\section{ROBOTS}
At the moment, none of the simulated robots are based on real robots, but the values for the various sensors, speeds, and sizes were chosen to be realistic. The mapping robots are loosely based on the Pioneer platform due to the range sensor coverage available to a circular base.

\subsection{Roles and Capabilities}
The system is based on the use of a heterogeneous swarm of scout robots and firefighting robots. The scouting robots will be equipped with standard IR sensors. The senor is assumed to take continuous distance reading and report the distance, the distance range is assumed to be 20cm (~8'') to 150cm (~60''). Also, standard sonar sensors will be utilized, the sensors will be able to detect objects from 0cm to 6.45meters (~254'') and provides sonar range information with 2.5cm (~1'') resolution. Finally, SICK LIDAR sensors may be employed, with a field of view of 360 ° and operating range of 0.1m to 20m.

\subsection{Noisy Measurements (SLAM)}
SLAM will be used to update the preloaded map within the known environment and at the same time keep track of the current location of each individual agent. The pseudocode is given below:

\begin{lstlisting}
foreach sensor in sensor_types[] {
   foreach sensor in array[] {
      sensor_matrix[m,n] = sensorProxy.scan[n] + normal(0, error);
   }
}
location = filter_noise(sensor_matrix[],time_slice);
\end{lstlisting}

\subsection{First Come First Serve (FCFS)}
With FCFS, fires will be attended to in the order they were reported. The pseudocode is given below:

\begin{lstlisting}
list fire_locations[];

foreach t in time {
   foreach robot in swarm[] {
      if(FOUND_FIRE_FLAG ==  True) {
         fire_locations.add(robot.location, robot.sensor.temp);
      }
   }
   foreach firefighter in swarm[] {
      if(fire_locations.size > 0) {
         goto(fire_locations[1]);
         pop(fire_locations[1]);
      }
   }
}
\end{lstlisting}

\subsection{Greedy Algorithm}
With the greedy algorithm, the room with the most reported fires will be attended to first. The pseudocode is given below:

\begin{lstlisting}
list rooms[];

while(1) {
   foreach robot in swarm[] {
      if(FOUND_FIRE_FLAG == True) {
         rooms[robot.get_room()] += 1;
      }
   }
   foreach firefighter in swarm[ {
      sorted_rooms = rooms.sort();
      if(sorted_rooms[1] > 0) {
         goto(sorted_rooms[1]);
         sorted_rooms[1] = 0;
      }
   }
}
\end{lstlisting}



\begin{figure}
	\begin{center}
		\leavevmode
		%\includegraphics{gantt_chart}
		\includegraphics[width=0.5\textwidth]{gantt_chart}
	\end{center}
	\caption{Gantt chart}
	\label{fig:gantt}
\end{figure}

%\includepdf{gantt_chart}

\section{TIMELINE}
The timeline of the project is broken up in eight (8) parts described below. For easy of understanding a Gantt chart is shown in the appendix with the proposed time allocation per task.

\subsection{Literature Review, Midterm Paper, Presentation}
The timeline of the project is broken up in eight (8) parts described below. For easy of understanding a Gantt chart is shown in the appendix with the proposed time allocation per task.

\subsection{Code Implementation and Debugging}
The code implementation begun after right after the midterm presentation, although preliminary work on the code begun earlier. The coding and debugging is given a 17 day period to be completed although it is believed that debugging will be until the end of simulations.

\subsection{Test Simulations}
An eight (8) day period is been allocated for the test simulations but five (5) of the days are overlapping with the code implementation and debugging. Testing will be extended until the day that the paper is due if needed although preferably it will be finished earlier to allow enough time for data analysis and statistical analysis of the simulations.

\subsection{Final Paper and Presentation}
The final paper is due on April 25 and it is given a six (6) days to be written and finalized. The paper will be started right after the code implementation is finished and in concurrence with the debugging and the test simulations. At the time the test simulations are finished the presentation will be put together in order to have a global and finalized view of the project. Also, there will be two days left after the paper is due, since the due date is on April 27, which will allow for the presentation to be finalized.


\section{FUTURE WORK}
In the future, the project would like to explore various mapping sensors in hopes of improving detection in worst-case scenarios. Another area to explore further is the use of sonar-like sensors, including WiFi in an effort to locate humans trapped inside buildings, not just fire (Compressive Cooperative Obstacle Mapping in Mobile Networks)

As a final step of the project implementation of a better map joining algorithm, in hopes of allowing this system to act as/alongside first responders.


\section{CONCLUSION}
After a literature review of similar projects and research of algorithms that can be incorporated into this project, it is determined that the timeline of the project can be implemented if the schedule is followed. This paper outlines the overview of the project goals and expectations. The results of simulations are expected to determine the feasibility, scalability and optimum operating number of agents in a medium sized floor plan.


\addcontentsline{toc}{section}{REFERENCES}
\nocite{*}
\bibliographystyle{ieeetr}
\bibliography{bib}

\end{document}

